# qlearningAgents.py
# ------------------
# Licensing Information: Please do not distribute or publish solutions to this
# project. You are free to use and extend these projects for educational
# purposes. The Pacman AI projects were developed at UC Berkeley, primarily by
# John DeNero (denero@cs.berkeley.edu) and Dan Klein (klein@cs.berkeley.edu).
# For more info, see http://inst.eecs.berkeley.edu/~cs188/sp09/pacman.html

from game import *
from learningAgents import ReinforcementAgent
from featureExtractors import *

import random,util,math

class QLearningAgent(ReinforcementAgent):
  """
    Q-Learning Agent

    Functions you should fill in:
      - getQValue
      - getAction
      - getValue
      - getPolicy
      - update

    Instance variables you have access to
      - self.epsilon (exploration prob)
      - self.alpha (learning rate)
      - self.discount (discount rate)

    Functions you should use
      - self.getLegalActions(state)
        which returns legal actions
        for a state
  """
  def __init__(self, **args):
    "You can initialize Q-values here..."
    ReinforcementAgent.__init__(self, **args)

    "*** YOUR CODE HERE ***"
    self.qValue = util.Counter()

  def getQValue(self, state, action):
    """
      Returns Q(state,action)
      Should return 0.0 if we never seen
      a state or (state,action) tuple
    """
    "*** YOUR CODE HERE ***"
    return self.qValue[(state,action)]
    #util.raiseNotDefined()


  def getValue(self, state):
    """
      Returns max_action Q(state,action)
      where the max is over legal actions.  Note that if
      there are no legal actions, which is the case at the
      terminal state, you should return a value of 0.0.
    """
    "*** YOUR CODE HERE ***"
    legalActions = self.getLegalActions(state)
    value = []
    for action in legalActions:
        value.append(self.getQValue(state, action))
    if len(value) == 0: 
        return 0.0
    return max(value)
    #util.raiseNotDefined()

  def getPolicy(self, state):
    """
      Compute the best action to take in a state.  Note that if there
      are no legal actions, which is the case at the terminal state,
      you should return None.
    """
    "*** YOUR CODE HERE ***"
    legalActions = self.getLegalActions(state)
    bestAction = None
    if len(legalActions) == 0:
        return bestAction
    maxValue = float("-infinity")
    for action in legalActions:
        qValue = self.getQValue(state, action)
        if qValue > maxValue:
            maxValue = qValue
            bestAction = action
        elif qValue == maxValue:
            bestAction = random.choice([action, bestAction])
    return bestAction    
    #util.raiseNotDefined()

  def getAction(self, state):
    """
      Compute the action to take in the current state.  With
      probability self.epsilon, we should take a random action and
      take the best policy action otherwise.  Note that if there are
      no legal actions, which is the case at the terminal state, you
      should choose None as the action.

      HINT: You might want to use util.flipCoin(prob)
      HINT: To pick randomly from a list, use random.choice(list)
    """
    # Pick Action
    legalActions = self.getLegalActions(state)
    action = None
    "*** YOUR CODE HERE ***"
    if len(legalActions) == 0:
        return action
    if util.flipCoin(self.epsilon):
        action = random.choice(legalActions)
    else:
        action = self.getPolicy(state)
    return action
    #util.raiseNotDefined()

  def update(self, state, action, nextState, reward):
    """
      The parent class calls this to observe a
      state = action => nextState and reward transition.
      You should do your Q-Value update here

      NOTE: You should never call this function,
      it will be called on your behalf
    """
    "*** YOUR CODE HERE ***"
    sample = reward + self.discount * self.getValue(nextState)
    self.qValue[state, action] = (1-self.alpha) * self.qValue[state, action] + self.alpha * sample
    #util.raiseNotDefined()

class PacmanQAgent(QLearningAgent):
  "Exactly the same as QLearningAgent, but with different default parameters"

  def __init__(self, epsilon=0.05,gamma=0.8,alpha=0.2, numTraining=0, **args):
    """
    These default parameters can be changed from the pacman.py command line.
    For example, to change the exploration rate, try:
        python pacman.py -p PacmanQLearningAgent -a epsilon=0.1

    alpha    - learning rate
    epsilon  - exploration rate
    gamma    - discount factor
    numTraining - number of training episodes, i.e. no learning after these many episodes
    """
    args['epsilon'] = epsilon
    args['gamma'] = gamma
    args['alpha'] = alpha
    args['numTraining'] = numTraining
    self.index = 0  # This is always Pacman
    QLearningAgent.__init__(self, **args)

  def getAction(self, state):
    """
    Simply calls the getAction method of QLearningAgent and then
    informs parent of action for Pacman.  Do not change or remove this
    method.
    """
    action = QLearningAgent.getAction(self,state)
    self.doAction(state,action)
    return action


class ApproximateQAgent(PacmanQAgent):
  """
     ApproximateQLearningAgent

     You should only have to overwrite getQValue
     and update.  All other QLearningAgent functions
     should work as is.
  """
  def __init__(self, extractor='IdentityExtractor', **args):
    self.featExtractor = util.lookup(extractor, globals())()
    PacmanQAgent.__init__(self, **args)

    # You might want to initialize weights here.
    "*** YOUR CODE HERE ***"
    self.qValue = util.Counter()
    self.weightValues = pickleReadWeightValue()
    
    print "init() self.weightValues: ", self.weightValues

  def getQValue(self, state, action):
    """
      Should return Q(state,action) = w * featureVector
      where * is the dotProduct operator
    """
    "*** YOUR CODE HERE ***"
    self.qValue[(state,action)] = self.featExtractor.getFeatures(state,action) * self.weightValues
    return self.qValue[(state,action)]
    #util.raiseNotDefined()

  def update(self, state, action, nextState, reward):
    """
       Should update your weights based on transition
    """
    "*** YOUR CODE HERE ***"
    correction = (reward + self.discount * self.getValue(nextState)) - self.qValue[(state, action)]#self.getQValue(state, action)
    featureValues = self.featExtractor.getFeatures(state,action)
    for feature in featureValues:
        self.weightValues[feature] = self.weightValues[feature] + self.alpha * correction * featureValues[feature]
    #util.raiseNotDefined()

  def final(self, state):
    "Called at the end of each game."
    # call the super-class final method
    PacmanQAgent.final(self, state)

    # did we finish training?
    if self.episodesSoFar == self.numTraining:
      # you might want to print your weights here for debugging
      "*** YOUR CODE HERE ***"
      print "self.weightValues: ", self.weightValues
      pickleWriteWeightValuePersist(self.weightValues)
      pass

def pickleWriteWeightValuePersist(weightValues):
    import pickle
    file1 = open('DataFile_Pacman','w+')
    pickle.dump(weightValues,file1)
    file1.close()
    
def pickleReadWeightValue():
    import pickle
    weightValues = {}
    try: 
        file1 = open('DataFile_Pacman','r')
        weightValues = pickle.load(file1)
    except IOError:
        weightValues = util.Counter()
        #continue
    return weightValues

def writeWeightValuePersist(weightValues):
    text = {}
    try:
        file = open("weightValues.txt", "w")
        text = str(weightValues)
        try:
            file.writelines(text)
        finally:
            file.close()
    except IOError:
        pass

def readWeightValue():
    weightValues = {}
    try:
        file = open("weightValues.txt", "r")
        try:
            text = file.read() 
            weightValues = eval(text)
        finally:
            file.close()
    except IOError:
        pass
    return weightValues

class ComplexExtractor(FeatureExtractor):
  """
  Returns complex features for a basic reflex Pacman:
  - whether food will be eaten
  - how far away the next food is
  - whether a ghost collision is imminent
  - whether a ghost is one step away
  -
  - whether capsule will be eaten
  """
  
  def getFeatures(self, state, action):
    # extract the grid of food and wall locations and get the ghost locations
    food = state.getFood()
    walls = state.getWalls()
    ghosts = state.getGhostPositions()
    capsules = state.getCapsules()
    ghostsStates = state.getGhostStates()
    pacmanState = state.getPacmanState()

    features = util.Counter()
    
    features["bias"] = 1.0
    
    # compute the location of pacman after he takes the action
    x, y = state.getPacmanPosition()
    dx, dy = Actions.directionToVector(action)
    next_x, next_y = int(x + dx), int(y + dy)
    
    # count the number of ghosts 1-step away
    #features["#-of-ghosts-1-step-away"] = sum((next_x, next_y) in Actions.getLegalNeighbors(g, walls) for g in ghosts)
    #print "ghosts: ", ghosts
    features["#-of-ghosts-1-step-away"] = sum((next_x, next_y) in Actions.getLegalNeighbors(ghostState.configuration.pos, walls) for ghostState in ghostsStates if ghostState.scaredTimer < 2)
    
    #features["closest-scared-ghost"] = sum((next_x, next_y) in Actions.getLegalNeighbors(ghostState.configuration.pos, walls) for ghostState in ghostsStates if ghostState.scaredTimer > 2)
    
    # if there is no danger of ghosts then add the food feature
    if not features["#-of-ghosts-1-step-away"] and food[next_x][next_y]:
      features["eats-food"] = 1.0
      
    #print "capsules: ", capsules, "food: ", food
    if not features["#-of-ghosts-1-step-away"] and (next_x,next_y) in capsules:
      features["eats-capsule"] = 0.5
      
    if not features["#-of-ghosts-1-step-away"] and (next_x,next_y) in [ghostState.configuration.pos for ghostState in ghostsStates if ghostState.scaredTimer > 2]:
      features["eats-ghost"] = 1.5
    
    dist = closestFood((next_x, next_y), food, walls)
    if dist is not None:
      # make the distance a number less than one otherwise the update
      # will diverge wildly
      features["closest-food"] = float(dist) / (walls.width * walls.height) 
    
    distCap = closestCapsule((next_x, next_y), capsules, walls)
    if distCap is not None:
      # make the distance a number less than one otherwise the update
      # will diverge wildly
      capPoint = (float(distCap) / (walls.width * walls.height))/2
      #if len([ghostState for ghostState in ghostsStates if ghostState.scaredTimer > 10]) > 0:
      #    capPoint = capPoint/10
      features["closest-capsule"] = capPoint
      #print "distCap: ", distCap
    
    distScaredGhost = closestScaredGhost((next_x, next_y), ghostsStates, walls)
    if distScaredGhost is not None:
        features["closest-ScaredGhost"] = (float(distScaredGhost) / (walls.width * walls.height))*2
    
    distGhost = closestGhost((next_x, next_y), ghostsStates, walls)
    possibleActions = Actions.getPossibleActions(pacmanState.configuration, walls)
    if Directions.STOP in possibleActions:
        possibleActions.remove(Directions.STOP)
        
    legalNeighbors = Actions.getLegalNeighbors((next_x, next_y), walls)
    #print "legalNeighbors: ", legalNeighbors, "possibleActions: ", possibleActions, "Pos: ", (next_x, next_y)
    distExit = closestExit((next_x, next_y), ghostsStates, walls)
    #if len(possibleActions) < 3 and distGhost is not None and distExit is not None:
    #    features["2way-tunel"] =  ((float(distGhost)-float(distExit)) / (walls.width * walls.height))
    #    features["closestExit-tunel"] =  (float(distExit) / (walls.width * walls.height))
    
    features.divideAll(10.0)
    return features

def closestCapsule(pos, capsules, walls):
  """
  closestCapsule -- this is similar to the function that we have
  worked on in the search project; here its all in one place
  """
  fringe = [(pos[0], pos[1], 0)]
  expanded = set()
  while fringe:
    pos_x, pos_y, dist = fringe.pop(0)
    if (pos_x, pos_y) in expanded:
      continue
    expanded.add((pos_x, pos_y))
    # if we find a capsule at this location then exit
    if (pos_x,pos_y) in capsules:
      return dist
    # otherwise spread out from the location to its neighbours
    nbrs = Actions.getLegalNeighbors((pos_x, pos_y), walls)
    for nbr_x, nbr_y in nbrs:
      fringe.append((nbr_x, nbr_y, dist+1))
  # no capsule found
  return None
  
def closestScaredGhost(pos, ghostsStates, walls):
  """
  closestScaredGhost -- this is similar to the function that we have
  worked on in the search project; here its all in one place
  """
  fringe = [(pos[0], pos[1], 0)]
  expanded = set()
  while fringe:
    pos_x, pos_y, dist = fringe.pop(0)
    if (pos_x, pos_y) in expanded:
      continue
    expanded.add((pos_x, pos_y))
    # if we find a capsule at this location then exit
    if (pos_x,pos_y) in [ghostState.configuration.pos for ghostState in ghostsStates if ghostState.scaredTimer > 2]:
      #print "dist: ", dist
      return dist
    # otherwise spread out from the location to its neighbours
    nbrs = Actions.getLegalNeighbors((pos_x, pos_y), walls)
    for nbr_x, nbr_y in nbrs:
      fringe.append((nbr_x, nbr_y, dist+1))
  # no capsule found
  return None
  
def closestGhost(pos, ghostsStates, walls):
  """
  closestGhost -- this is similar to the function that we have
  worked on in the search project; here its all in one place
  """
  fringe = [(pos[0], pos[1], 0)]
  expanded = set()
  while fringe:
    pos_x, pos_y, dist = fringe.pop(0)
    if (pos_x, pos_y) in expanded:
      continue
    expanded.add((pos_x, pos_y))
    # if we find a capsule at this location then exit
    if (pos_x,pos_y) in [ghostState.configuration.pos for ghostState in ghostsStates]:
      #print "dist: ", dist
      return dist
    # otherwise spread out from the location to its neighbours
    nbrs = Actions.getLegalNeighbors((pos_x, pos_y), walls)
    for nbr_x, nbr_y in nbrs:
      fringe.append((nbr_x, nbr_y, dist+1))
  # no capsule found
  return None
  
def closestExit(pos, ghostsStates, walls):
  """
  closestExit -- this is similar to the function that we have
  worked on in the search project; here its all in one place
  """
  fringe = [(pos[0], pos[1], 0)]
  expanded = set()
  while fringe:
    pos_x, pos_y, dist = fringe.pop(0)
    if (pos_x, pos_y) in expanded:
      continue
    expanded.add((pos_x, pos_y))
    # if we find a capsule at this location then exit
    possibleActions = getLegalActions((pos_x, pos_y), walls)
    if Directions.STOP in possibleActions:
        possibleActions.remove(Directions.STOP)
    if len(possibleActions) > 2:
      #print "dist: ", dist
      return dist
    # otherwise spread out from the location to its neighbours
    nbrs = Actions.getLegalNeighbors((pos_x, pos_y), walls)
    for nbr_x, nbr_y in nbrs:
      fringe.append((nbr_x, nbr_y, dist+1))
  # no capsule found
  return None
  
def getLegalActions(pos, walls):
        possible = []
        x, y = pos
        x_int, y_int = int(x + 0.5), int(y + 0.5)

        # In between grid points, all agents must continue straight
        #if (abs(x - x_int) + abs(y - y_int)  > Actions.TOLERANCE):
           #return [config.getDirection()]

        for dir, vec in Actions._directionsAsList:
            dx, dy = vec
            next_y = y_int + dy
            next_x = x_int + dx
            if not walls[next_x][next_y]: possible.append(dir)

        return possible
